3. DFT, DFS, FFT 总结

3.1 信号与空间

$\mathbb V$ ：可以定义加法、标量乘法、满足交换律、结合律、分配律、存在加法零元、加法逆元、乘法单位元。

向量的内积 定义为：

⟨ \cdot, \cdot ⟩ : V \times V \to F

内积用于测量向量间的相似性。如果内积为零，则称向量是正交的。

内积满足的特性：分配性、共轭对称性、标度性、正定性、正交性。

$\R^n$ $\displaystyle \sum_{n=0}^{N-1} x_ny_n$ .
$\C^N$ $\displaystyle \sum_{n=0}^{N-1} x_n^*y_n$ .
$L_2([-1,1])$ $\displaystyle \int_{-1}^{1} x(t)y(t)\mathrm d t$ .

信号空间 $\C^N$ 空间中：

x = [x_{0}, x_{1}, \dots, x_{N - 1}]^{⊤}

$\displaystyle \left\langle\bold x,\bold y\right\rangle=\displaystyle \sum_{n=0}^{N-1} x_n^*y_n$
$\displaystyle \left\langle\bold x,\bold y\right\rangle=\displaystyle \sum_{n=-\infin}^{\infin} x_n^*y_n$

要求序列是平方可加的。

基向量 $\mathbb H$ $\{\bold w^{(k)}\}$ ，包含最少的向量数，使得其他任意向量空间中的向量都可以写成这些向量的线性组合。

也就是满足以下条件，

x = \sum_{k = 0}^{K - 1} α_{k} w^{(k)}, α_{k} \in C

$\alpha_k$ 是唯一的。并且基向量之间线性无关。

$\left\langle \bold w^{(k)},\bold w^{(n)}\right\rangle=0$ $k\not= n$ .
$\left\langle \bold w^{(k)},\bold w^{(n)}\right\rangle=\delta[n-k]$ .
当基向量归一化的时候，基系数计算简单，
$α_{k} = ⟨ w^{(k)}, x ⟩$
但是当正交基未归一化时，不能直接使用这个方法计算。

$[-1,1]$ 区间的傅里叶基函数：

\frac{1}{\sqrt{2}}, \cos π t, \sin π t, \cos 2 π t, \sin 2 π t, \dots

$h(t)=\operatorname{sgn}(t)$ ，使用：

\hat{h} (t) = \sum_{k = 0}^{N} \frac{1}{2 k + 1} \sin [(2 k + 1) π t]

近似。近似的结果满足均方收敛的条件，但是非一致收敛。

3.2 DFT

DFT 在信号空间中的表征 由时域基转换到了频域基：

[w^{(k)}]_{n} = e^{j \frac{2 π}{N} k n}

可以证明是正交的，但是没有进行归一化. DFT 矩阵：

W_{N} = [w^{(0)}, \dots, w^{(n - 1)}]^{H}

DFT 公式：

[X]_{k} = ⟨ w^{(k)}, x ⟩ \Rightarrow X = W_{N} x

IDFT 公式：

x = \frac{1}{N} W_{N}^{H} X

DFT 公式和 IDFT 公式

\begin{matrix} X [k] = \sum_{n = 0}^{N - 1} x [n] e^{- j \frac{2 π}{N} k n}, k = 0, 1, \dots, N - 1 \\ x [n] = \frac{1}{N} \sum_{k = 0}^{N - 1} X [k] e^{j \frac{2 π}{N} k n}, n = 0, 1, \dots, N - 1 \end{matrix}

DFT 示例：余弦序列

当相位为零，

x [n] = 3 \cos (\frac{2 π \cdot 4 n}{64}), x [n] \in C^{64}

ω = \frac{2 π \cdot k}{N}

x [n] = \frac{3}{2} (w_{4} [n] + w_{60} [n])

X [k] = ⟨ w_{k} [n], x [n] ⟩ = 96 (δ [k - 4] + δ [k - 60])

$w_k[n]$ 未进行归一化。

当相位不为零，

x [n] = 3 \cos (\frac{2 π \cdot 4 n}{64} + \frac{π}{3}), x [n] \in C^{64}

x [n] = \frac{3}{2} (e^{j π / 3} w_{4} [n] + e^{- j π / 3} w_{60} [n])

X [k] = ⟨ w_{k} [n], x [n] ⟩ = 96 e^{j π / 3} δ [k - 4] + 96 e^{- j π / 3} δ [k - 60]

幅值不变，相角发生了变化。

DFT 示例：矩形窗信号 $M$ $N$ 长的矩形信号。

X [k] = \frac{\sin (\frac{π}{N} M k)}{\sin (\frac{π}{N} k)} e^{- j \frac{π}{N} (M - 1) k}

$X[0]=M$ $Mk/N$ $X[k]=0$ .

3.3 DFS

\begin{matrix} \tilde{X} (k) = DFS {\tilde{x} (n)} = \sum_{n = 0}^{N - 1} \tilde{x} (n) e^{- j \frac{2 π}{N} n k} = \sum_{n = 0}^{N - 1} \tilde{x} (n) W_{N}^{n k} \\ \tilde{x} (n) = IDFS {\tilde{X} (k)} = \frac{1}{N} \sum_{k = 0}^{N - 1} \tilde{X} (k) e^{j \frac{2 π}{N} n k} = \frac{1}{N} \sum_{k = 0}^{N - 1} \tilde{X} (k) W_{N}^{- n k} \end{matrix}

圆周位移

\tilde{x} [n - M] R_{N} [n] = x [\mod (n - m, N)]

3.4 DFT 性质

周期序列的移位：
$DFT {x [(n + m)_{N}]} = W_{N}^{- m k} X (k) = e^{j \frac{2 π}{N} m k} X (k)$
幅度不变，相角位移。
$IDFT {X [(k + m)_{N}]} = e^{- j \frac{2 π}{N} m n} x [n]$
圆周翻转特性：
$\begin{matrix} DFT {x [(- n)_{N}]} = X [(- k)_{N}] \\ DFT {x^{*} [(- n)_{N}]} = X^{*} [(k)_{N}] \end{matrix}$
圆周共轭对称/反对称序列 的分解：
- $x_{ep}[n]=x_{ep}^*[(-n)_N]$ （全为实数且对称的序列是圆周共轭对称序列）
- $x_{op}[n]=-x_{op}^*[(-n)_N]$ .
$x [n] = x_{e p} [n] + x_{o p} [n]$
${\begin{cases} x_{e p} [n] = \frac{1}{2} (x [n] + x^{*} [(- n)_{N}]) \\ x_{o p} [n] = \frac{1}{2} (x [n] - x^{*} [(- n)_{N}]) \end{cases}$
对于时域和频域，一方分解为实部+虚部，另一方分解为对称+反对称，互相对应。需要记忆共轭对称分量的形式和共轭反对称分量的形式。
特别地，如果时域只有实部部分，则对应频域只有对称部分，满足：
$\begin{matrix} X [k] = X^{*} [(- k)_{N}] \Rightarrow {\begin{cases} | X (k) | = | X (N - k) | \\ \arg X (k) = - \arg X (N - k) \end{cases} \end{matrix}$
利用圆周共轭对称性可以减少实序列 DFT 的计算量。
例如 用一次复数序列的 DFT 来求得两个实数序列的 DFT，我们构造复数序列：
$x [n] = x_{1} [n] + j x_{2} [n]$
$x_{1,2}[n]$ 为实数序列，则共轭对称分量和共轭反对称分量分别为：
$\begin{matrix} X_{e p} [k] = DFT {x_{1} [n]}, \\ X_{o p} [k] = DFT {j x_{2} [n]} \Rightarrow DFT {x_{2} [n]} = \frac{1}{j} X_{o p} [k] \end{matrix}$
$\boldsymbol N$ $\boldsymbol{2N}$ $x[n]$ 的 DFT $x_1,x_2$ .
$\begin{matrix} x [n] = {\begin{cases} x_{1} [k], & n = 2 k \\ x_{2} [k], & n = 2 k + 1 \end{cases} \end{matrix}$
$y[n]=x_1[n]+jx_2[n]$ 利用：
${\begin{cases} DFT {x_{1} [n]} = Y_{e p} [k] = (Y [k] + Y^{*} [(- k)_{N}]) / 2 \\ DFT {x_{2} [n]} = - j Y_{o p} [k] = - j (Y [k] - Y^{*} [(- k)_{N}]) / 2 \end{cases}$
$X_1[k]$ $X_2[k]$ . 根据 DFT 定义，
$\begin{aligned} X [k] & = \sum_{n even} x_{1} [n] W_{2 N}^{n k} + \sum_{n odd} x_{2} [n] W_{2 N}^{n k} \\ = \sum_{n even} x_{1} [n] W_{N}^{\frac{n}{2} k} + W_{2 N}^{k} \sum_{n odd} x_{2} [n] W_{N}^{\frac{n - 1}{2} k} \\ = X_{1} [k] + W_{2 N}^{k} X_{2} [k], k = 0, 1, \dots, N - 1 \end{aligned}$
$\begin{matrix} X [k + N] = X_{1} [k] + W_{2 N}^{k + N} X_{2} [k] \\ = X_{1} [k] - W_{2 N}^{k} X_{2} [k], k = 0, 1, \dots, N - 1 \end{matrix}$
Parseval 定理：
$\sum_{n = 0}^{N - 1} | x (n) |^{2} = \frac{1}{N} \sum_{k = 0}^{N - 1} | X (k) |^{2}$
$x(n)$ 为实序列，则
$\sum_{n = 0}^{N - 1} x^{2} (n) = \frac{1}{N} \sum_{k = 0}^{N - 1} | X (k) |^{2}$
要点：计算模长。
圆周卷积和 定义：
$y [n] = \sum_{m = 0}^{L - 1} x_{1} [m] x_{2} [(n - m)_{L}]$ $Y [k] = X_{1} [k] X_{2} [k]$
$x_1[n]$ $x_2[n]$ $L$ $y[n]=x_1[n]x_2[n]$ ，可得
$Y [k] = \frac{1}{L} X_{1} [k] *_{L} X_{2} [k]$
线性卷积和和圆周卷积和的关系 $L$ $L$ 点圆周卷积和。

例题 $x(n)=\{3,2,0,2\}$ $h(n)=\{4,-2,1,-1\}$ 的圆周卷积和，可以使用比较简便的方法：
$x(n)$ 3 2 0 2 $y(n)$
$h((-n)_4)$ 4 -1 1 -2 6
$h((1-n)_4)$ -2 4 -1 1 4
$h((2-n)_4)$ 1 -2 4 -1 -3
$h((3-n)_4)$ -1 1 -2 4 7
可得：
$y (n) = {6, 4, - 3, 7}$

$x(n)$	3	2	0	2	$y(n)$
$h((-n)_4)$	4	-1	1	-2	6
$h((1-n)_4)$	-2	4	-1	1	4
$h((2-n)_4)$	1	-2	4	-1	-3
$h((3-n)_4)$	-1	1	-2	4	7

例题已知有限长序列为
$x (n) = δ (n - 2) + 4 δ (n - 4)$
求其 8 点 DFT；
$\begin{matrix} X (k) = \sum_{n = 0}^{N - 1} x (n) W_{N}^{n k} \\ = W_{N}^{2 k} + 4 W_{N}^{4 k} = (- j)^{k} + 4 (- 1)^{k} \end{matrix}$
$X(0\sim 7)$ .
$h(n)$ $H(k)=W_{8}^{-3k}X(k)$ $h(n)$ .
$\begin{matrix} H (k) = \sum_{n = 0}^{N - 1} x (n) W_{N}^{(n - 3) k} = \sum_{n = ⟨ N ⟩} x ((n + 3)_{N}) W_{N}^{n k} \end{matrix}$ $h (n) = δ (n - 7) + 4 δ (n - 1)$
$y(n)$ $Y(k)=X(k)H(k)$ $y(n)$ .
$y (n) = δ (n - 1) + 8 δ (n - 3) + 16 δ (n - 5)$

3.5 傅里叶变换的各种可能形式

3.6 频域采样定理

$x[n]\in l_2(\Z)$ $X(e^{j\omega})\in L_2(\R)$ ，表达式为：

X (e^{j ω}) = \sum_{n = - \infty}^{\infty} x [n] e^{- j ω n}

$N$ 点：

\tilde{X} [k] = X (e^{j ω}) |_{ω = 2 π k / N} = \sum_{n = - \infty}^{\infty} x [n] W_{N}^{k n}

进行 IDFS 还原：

\tilde{x} [n] = \frac{1}{N} \sum_{n = - \infty}^{\infty} \tilde{X} [k] W_{N}^{- k n}

$x[n]$ $\tilde{x}[n]$ 的关系。展开可得：

\begin{aligned} \tilde{x} [n] & = \frac{1}{N} \sum_{n = - \infty}^{\infty} \tilde{X} [k] e^{j k \frac{2 π}{N} n} \\ = \frac{1}{N} \sum_{n = - \infty}^{\infty} (\sum_{m = - \infty}^{\infty} x [m] W_{N}^{k m}) W_{N}^{- k n} \\ = \sum_{m = - \infty}^{\infty} x [m] (\frac{1}{N} \sum_{k = 0}^{N - 1} W_{N}^{k (m - n)}) \end{aligned}

$m-n$ $N$ 的倍数的时候后面一项等于一，否则等于零，

\tilde{x} [n] = \sum_{r = - \infty}^{\infty} x [n + r N]

$\tilde{x}[n]$ $x[n]$ 的关系： $\boldsymbol{\tilde{x}[n]}$ $\boldsymbol{x[n]}$ $N$ .

研究周期延拓造成的混叠现象：

$x[n]$ $\tilde{x}[n]\not=x[n]$ $N$ 越大，失真越小。
$x[n]$ 有限支持区域长度 $M$ .
- $N\ge M$ $\tilde{x}[n]$ $x[n]$ ；
- $N<M$ $\tilde x[n]$ $x[n]$ .

频域采样定理：

$N$ $M$ $0\sim M-1$ $N\ge M$ $\tilde{X}[k]$ $\tilde{x}[n]$ ，满足

\tilde{x} [n] R_{N} [n] = x [n] R_{N} [n]

$\tilde{X}[k]$ $x[n]$ ，否则产生时域混叠现象。

由此可得，频域抽样产生时域的周期延拓，而时域抽样产生频域的周期延拓。

频域插值重构 $X(k)|_{z=e^{j2\pi \frac{k}{N}}}$ $X(z)$ .

\begin{aligned} X (z) & = \sum_{n = 0}^{N - 1} x (n) z^{- n} \\ = \sum_{n = 0}^{N - 1} [\frac{1}{N} \sum_{k = 0}^{N - 1} X (k) W_{N}^{- n k}] z^{- n} \\ = \frac{1}{N} \sum_{k = 0}^{N - 1} X (k) [\sum_{n = 0}^{N - 1} W_{N}^{- n k} z^{- n}] \\ = \frac{1}{N} \sum_{k = 0}^{N - 1} X (k) \frac{1 - W_{N}^{- N k} z^{- N}}{1 - W_{N}^{- k} z^{- 1}} \\ = \frac{1 - z^{- N}}{N} \sum_{k = 0}^{N - 1} \frac{X (k)}{1 - W_{N}^{- k} z^{- 1}} \\ = \sum_{k = 0}^{N - 1} X (k) Φ_{k} (z) \end{aligned}

插值函数：

Φ_{k} (z) = \frac{z^{N} - 1}{N z^{N - 1} (z - W_{N}^{- k})}

Φ (z) |_{z = W_{N}^{- r}} = δ (r - k)

$z=W_{N}^{-r},r=0,1,2,\cdots,k-1,k+1,\cdots,N-1$ .

$z=e^{j\omega}$ $\Phi_k(z)$ 可得

Φ (ω) = \frac{1}{N} \frac{\sin (ω N / 2)}{\sin (ω / 2)} e^{- j (N - 1) ω / 2}

$X(z)$ 表达式为：

Φ (z) = \sum_{k = 0}^{N - 1} X (k) Φ (ω - 2 π k / N)

3.7 非周期连续时间信号谱分析

3.7.1 时域采样

$f_s\ge 2f_h$ $f_h$ $f_s=(3\sim 6)f_h$ . 如果不是带限信号，需要加入防混叠滤波器。

当抽样频率不符合要求时，会产生 频谱的混叠失真。

3.7.2 时域截断

可以看成原信号乘以窗函数：

\begin{matrix} d [n] = {\begin{cases} 1, & 0 \leq n \leq N - 1 \\ 0, & else . \end{cases} \end{matrix}

$100\mathrm{~Hz}$ $120 \mathrm{~Hz}$ 的谱线构成，经过加窗之后，卷积形成下面的频谱图。因为窗函数存在主瓣和旁瓣，且主瓣存在一定宽度，所以对频谱进行了一定程度的展宽，造成了频谱泄露的现象。

选择不同种类的窗函数，可以增大主旁瓣幅度比，从而减少 谱间干扰.
$32\mathrm{~dB}$ $8\pi/N$ 增加一倍，又会增加频谱泄露的程度。
$N$ ，可以减小主瓣宽度，从而减少 频谱泄露 的程度。

$N$ $x[n]$ 信号周期长度的整数倍时，会产生频谱泄露，反之不存在。

3.7.3 周期延拓

$M\ge N$ $M=N$ .

$N$ $T$ $NT=T_0$ ，可得频率分辨率为：

F_{0} = \frac{1}{T_{0}} = \frac{1}{N T} = \frac{f_{s}}{N}

频率分辨率越小，分辨接近频率信号的能力越强。

提高分辨率的方法：

$T_0$ $f_s$ 不变，抽样点数增加.
$M$ $N$ 值，不能提高分辨率。

$f_s/N$ $N$ $N$ 点抽样值中的任意相邻两点之间的频率点上的频谱值是不知道的，就好像是通过一个栅栏的缝隙观看一个镜像一样，称为 栅栏效应。

减小栅栏效应

$T_0$ $f_s$ $N$ 增多；
$T_0$ $N$ $M>N$ ；
$f_s$ $T_0$ $N$ .

3.7.4 计算 DFT

3.7.5 谱分析综合习题

分析信号：

x (t) = \cos (2 π f_{1} t) + \cos (2 π f_{2} t), f_{1} = 100 Hz, f_{2} = 120 Hz

$f_s=600\mathrm{~Hz}$ 对其进行采样。

$f_s>2f_h=240\mathrm{~Hz}$ 满足奈奎斯特采样条件；
$f_s/N$ $N\ge 30$ $1/20 \mathrm{~s}$ $Nf_s$ $1/20$ $N=30k$ ，才能没有频谱混叠。
$30$ 的倍数，则会产生频谱混叠效应。

分析信号：

x_{a} (t) = \cos (2 π f_{1} t) + \frac{1}{2} \cos (2 π f_{2} t) + \frac{1}{2} \cos (2 π f_{3} t)

$f_1=600\mathrm{~Hz},f_2=500\mathrm{~Hz},f_3=700\mathrm{~Hz}$ .

$f_s$ $f_s>2f_h$ $f_s$ $x[n]$ 是周期序列；
$N$ $NT_s=N/f_s$ 是原序列周期的整数倍，才能没有频谱泄露。
$\operatorname{gcd}(1/600,1/500,1/700)=1/100$ $f_s=2100\mathrm{~Hz}$ $N=21k$ ，才能没有频谱泄露。
$f_s=3\mathrm{~kHz}$ $N$ $N/f_s$ 不是原始周期的整数倍，所以会产生频谱泄露。
$f_s=3\mathrm{~kHz}$ 的情况下，既没有频谱泄露，又能分辨所有频率分量，要求：
$F_{0} = \frac{f_{s}}{N} \geq 100 Hz \frac{N}{f_{s}} 为 1 / 100 整数倍$
$N=30$ . 恰好可以分辨所有频率分量。

分析序列：

x [n] = \cos [0.48 π n] + \cos [0.52 π n]

$N=10$ $f_s$ $0.02 f_s$ ，
此时的频率分辨率为：
$F_{0} = \frac{f_{s}}{N} = 0.2 f_{s} > 0.02 f_{s}$
无法分辨频率分量；
$N=10$ $F_0=1/T_0$ $T_0$ 为有效数据的长度没有改变，所以频率分辨率没有改变，但是减少了栅栏效应。
$N=100$ $F_0=f_s/100=0.01 f_s<0.02f_s$ $N'=50$ $N=100$ $50$ 的倍数，所以没有频谱泄露。

分析正弦信号：

x (t) = \cos (2 π 100 t) + \cos (2 π 400 t)

$f_s=900\mathrm{~Hz}$ $N=64$ .

$x(n)$ $x(n)$ 的最小周期为多少？频率分辨率为多少 Hz?
$f_h=400\mathrm{~Hz}$ ，满足奈奎斯特条件：
$f_{s} > 2 f_{h}$
因此不会发生混叠。
$T_s=1/900 \mathrm{~s}$ ，则
$x (n) = x_{a} (n T_{s}) = \cos (\frac{2 π}{9} n) + \cos (\frac{8 π}{9} n)$
$x(n)$ $N=9$ .
频率分辨率可以通过下述表达式计算得到：
$F_{0} = \frac{1}{N T_{s}} = \frac{f_{s}}{N} = 14.0625 Hz$
$NT_s$ 可以理解为有效采样长度的时间。
$|Y(k)|$ $x(t)$ $x(n)$ 进行补零来达成目的，原因是什么？能否通过增加矩形窗的长度来达到目的，原因是什么？
频率响应的峰值点为：
$\frac{2 π}{9}, \frac{8 π}{9}$
$2\pi k/N$ $N$ $8$ $72$ $N=64$ $M=72$ ，窗函数零点不是一一对应，旁瓣对主瓣产生遮盖作用）
$\cos\left(\frac{2\pi}{9}n\right)+\cos\left(\frac{8\pi}{9}n\right)$ ，频率成分是一致的。
$\cos\left(\frac{7\pi}{36}n\right)+\cos\left(\frac{8\pi}{36}n\right)$ $N=20$ $M=36$ . 取点比较少，频率分辨率较高，且频率之间相差比较小，容易受到旁瓣干扰。
在这种情况下，可以增加窗的长度，提升谱分析的频率分辨率；选择其它旁瓣峰值衰减大的窗函数，减小对弱信号的掩盖
$N$ $x(t)$ $\operatorname{gcd}(1/100,1/400)=1/400$ $NT_s=k/100$ $N=72$ ，就可以使得频率成分一致。

3.8 FFT

3.8.1 DIT（时间抽取）算法

奇偶分组：
$\begin{matrix} x_{1} = {x [0], x [2], x [4], \dots, x [N - 2]} \\ x_{2} = {x [1], x [3], x [5], \dots, x [N - 1]} \end{matrix}$
$X_1[k],X_2[k]$ ,
$x$ 的 DFT 可以表示为：
$\begin{aligned} X [k] & = \sum_{n = 0}^{N - 1} x [n] W_{N}^{n k} \\ = \sum_{n = 0}^{N / 2 - 1} x [2 n] W_{N}^{2 n k} + \sum_{n = 0}^{N / 2 - 1} x [2 n + 1] W_{N}^{(2 n + 1) k} \\ = X_{1} [k] + W_{N}^{k} X_{2} [k] \end{aligned}$
前一半和后一半的输出：
${\begin{cases} X [k] = X_{1} [k] + W_{N}^{k} X_{2} [k] \\ X [N / 2 + k] = X_{1} [k] - W_{N}^{k} X_{2} [k] \end{cases}$
基本蝶形运算：
$N=8$ .
$x(0\sim 7)$ $N$ $k$ 乘以相应的倍数。

3.8.2 DIF（频率抽取）算法

对 DFT 表达式进行变换：
$\begin{aligned} X [k] & = \sum_{n = 0}^{N} x (n) W_{N}^{n k} \\ = \sum_{n = 0}^{N / 2 - 1} x (n) W_{N}^{n k} + x (n + N / 2) W_{N}^{(n + N / 2) k} \\ = \sum_{n = 0}^{N / 2 - 1} (x (n) + (- 1)^{k} x (n + N / 2)) W_{N}^{n k} \end{aligned}$
$X[k]$ $k$ 的奇偶性相关，所以有必要按照奇偶分组。
$k=2r$ ，代入表达式，得到：
$X_{1} [r] = X [2 r] = DFT {x (n) + x (n + N / 2)}$
$k=2r+1$ ，代入表达式，得到：
$X_{2} [r] = X [2 r + 1] = DFT {(x (n) - x (n + N / 2)) W_{N}^{n}}$
基本蝶形运算：
$N=8$ .

3.8.3 运算次数统计

$\log_2 N$ .
$N/2$ $N/2\log _2 N$ .
$N\log_2N$ .
$N/2\log_2 N$ $\pm1,\pm j$ ，需要对应减去。
$N\log_2N$ .

3.8.4 矩阵分解视角

DIT 算法

\begin{matrix} W_{8} = (\begin{matrix} I_{4} & I_{4} \\ I_{4} & - I_{4} \end{matrix}) (\begin{matrix} I_{4} & 0_{4} \\ 0_{4} & Λ_{4} \end{matrix}) (\begin{matrix} W_{4} & 0_{4} \\ 0_{4} & W_{4} \end{matrix}) D_{8} \end{matrix}

从蝶形图的角度也可以得到：

DIF 算法

\begin{matrix} W_{8} = D_{8}^{⊤} (\begin{matrix} W_{4} & 0_{4} \\ 0_{4} & W_{4} \end{matrix}) (\begin{matrix} I_{4} & 0_{4} \\ 0_{4} & Λ_{4} \end{matrix}) (\begin{matrix} I_{4} & I_{4} \\ I_{4} & - I_{4} \end{matrix}) \end{matrix}

对称阵转置后也相等，证明 DIT 和 DIF 是等价的。